package gold.gold02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 层序遍历, 先右后左
 * dfs实现层序遍历
 */
public class S0403特定深度链表 {
    /**
     * 99,
     */
    List<ListNode> totalNode;
    // 要么遍历一遍获得深度创建ListNode[], 要么不知道深度, 使用ArrayList<ListNode>, 但是还是要转回ListNode[], 有点麻烦。
    public ListNode[] listOfDepth(TreeNode tree) {
        if(tree == null) return null;
        totalNode = new ArrayList<>();
        putNode(tree, 0);
        // ListNode[] result = (ListNode[])totalNode.toArray();这样是不行的, 还是得先创建一个数组
         ListNode[] result = new ListNode[totalNode.size()];
        // 知道size的话从List往[]转还是比较简单的。
         totalNode.toArray(result);


        return result;
    }
    // 如果是每次都往上一个ListNode的next插入, 那么要么插入的时候找到最后一个点, 要么插入结束之后再反转这一串node
    // 可以先中再右再左, 这样就不用反转了。
    private void putNode(TreeNode curNode, int depth){
        if(curNode == null) return;
        if(totalNode.size() < depth + 1){
            // 这一层的第一个,
            totalNode.add(new ListNode(curNode.val));
        }else {
            // 节点插到队首
            ListNode tempNode = totalNode.get(depth);
            ListNode tempCurNode = new ListNode(curNode.val);
            tempCurNode.next = tempNode;
            totalNode.set(depth, tempCurNode);
        }
        // 先右再左, 这个其实不是层序, 是dfs, 但是因为按层插入, 所以结果是层序
        putNode(curNode.right, depth + 1);
        putNode(curNode.left, depth + 1);
    }

    public static void main(String[] args) {
        Integer[] array = new Integer[3];
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(1);
        list.add(1);
//        list.add(1);
//        list.add(1);
//        list.add(1);
        list.toArray(array);
        // size对不上的话，会传不进去
        System.out.println(Arrays.toString(array));
    }
}


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}